public class code1 {
//    top 101 链表相加（二）

    // write code here
    // 针对这里的问题，我们可以尝试使用 栈 的 先进后出 特性来解决问题
    // 先来定义两个栈
    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();
    // 之后在这里定义出两个指针，分别指向两个链表，便于后续遍历
    ListNode cur1 = head1;
    ListNode cur2 = head2;

    // 通过循环遍历，将两个链表分别存储到栈中
        while(cur1 != null) {
        stack1.push(cur1.val);
        cur1 = cur1.next;
    }
        while(cur2 != null) {
        stack2.push(cur2.val);
        cur2 = cur2.next;
    }

    // 之后再加减操作上，需要考虑一个进位问题，所以先设置一个标记
    int flag = 0;
    // 创建出两个新的节点用来组成新的链表
    ListNode newList = null;
    ListNode Head = null;

    // 通过 while 循环来实现相加将两个链表组合
        while(!stack1.isEmpty() || !stack2.isEmpty() || flag != 0) {
        int a = 0;
        int b = 0;
        // 进行两个栈的元素出栈判断
        if(stack1.isEmpty()){
            a = 0;
        }else {
            a = stack1.pop();
        }
        if(stack2.isEmpty()) {
            b = 0;
        }else {
            b = stack2.pop();
        }

        // 将两数进行相加 操作
        int c = a + b + flag;
        // 这里获取到两数相加后的进位数
        flag = c / 10;

        // 之后实现组建新链表
        newList = new ListNode(c % 10);
        newList.next = Head;
        Head = newList;
    }
        return Head;
}
}
